A network switch (or router or other packet forwarding or data generating device) may receive packets or other communications at rates exceeding hundreds, if not thousands, of packets per second. To insure a fair allocation of network resources (e.g., bandwidth), or to insure that resources are allocated in accordance with a desired policy, a network switch typically implements some type of packet transmission mechanism that determines when packets are selected for transmission. A conventional packet transmission mechanism will generally attempt to allocate bandwidth amongst all packet flows in a consistent manner, while preventing any one source from usurping too large a share—or an unauthorized share—of the network resources (e.g., by transmitting at a high data rate and/or by transmitting packets of relatively large size).
A typical network switch includes a number of packet queues, wherein each queue is associated with a specific flow or class of packet flows. As used herein, a “flow” is a series of packets that share at least some common header characteristics (e.g., packets flowing between two specific addresses). When packets arrive at the switch, the flow to which the packet belongs is identified (e.g., by accessing the packet's header data), and the packet (or a pointer to a location of the packet in a memory buffer) is stored in the corresponding queue. Enqueued packets are then selected for transmission according to a desired policy. For example, a number of queues may be serviced one-by-one in a round-robin manner; however, such a simple round-robin transmission scheme does not take into account packet size, and a source of packets could acquire bandwidth by simply transmitting packets of a large size.
To overcome the deficiencies of the simple round-robin method described above, a method known as “deficit round-robin” has been proposed. In a deficit round-robin packet transmission scheme, a number of packet queues are serviced one by one in a round-robin manner, wherein one pass through each active queue (i.e., a non-empty queue) is referred to as a “round.” For each round, a queue is allocated a quantum of bandwidth, which may be expressed as a specified quantity of data (e.g., 256 bytes). The quantums for a number of queues (or packet flows) may be the same or, alternatively, a set of queues may have different quantums (e.g., to implement quality of service or other resource reservation schemes). Also, a “deficit count” is maintained for each queue, and the deficit count for a queue during any given round is equal to the sum of any remaining deficit count from the preceding round plus the quantum for that queue. Accordingly, the usable bandwidth by a queue during a round is the current value of the deficit count (i.e., the prior deficit count plus the quantum).
When a queue is serviced during a round, the packet at the head of the queue is accessed to determine the packet's size, and if the packet's size is less than or equal to the current deficit count, the packet is dequeued for transmission. The size of the dequeued packet is subtracted from the deficit count, and if the updated value of the deficit count is greater than or equal to the next packet in that queue (if any), the next packet is also dequeued for transmission and the deficit count again updated. So long as a queue has remaining bandwidth in the current round—as determined by the queue's deficit count—the queue may continue to dequeue packets for transmission. Conversely, if the packet at the head of the queue (or any subsequent packet, if the lead packet has already been dequeued) has a size exceeding the current deficit count of the queue—i.e., the queue has utilized its allocated bandwidth in the current round—a packet (or an additional packet) is not dequeued from this queue during the current round. However, the queue's unutilized bandwidth, as expressed by the queue's deficit count, is carried over to the next round. An example of the above-described deficit round-robin method is presented in M. Shreedhar et al., Efficient Fair Queuing Using Deficit Round Robin, Proceedings ACM SIGCOMM, pp. 231-242, 1995.
The deficit round-robin scheme described above provides an approximation of another technique for scheduling packets known as Weighted Fair Queuing (WFQ). The WFQ scheduling technique may provide guaranteed services for a given number of sessions sharing the same link. WFQ is itself an approximation of Generalized Processor Sharing (GPS). GPS is defined using a fluid model in which packets are considered to be infinitely divisible. According to the GPS scheme, at any instant, each active session is served with a minimum rate equal to that session's reserved rate. Excess bandwidth available from inactive sessions (e.g., those with empty queues) is distributed among all active sessions at each instant in proportion to their individual reservations. For example, where each session is apportioned an equal share of the available bandwidth on a link and there are N active queues, the active sessions are served simultaneously, each at 1/N the link speed. Because GPS serves a small portion of a packet at a time, this scheme can, in practice, be difficult to implement.
WFQ is a packet-by-packet version of the GPS algorithm. A virtual finish time is calculated for each packet, and packets are sorted in a priority order according to their finish times. Packets are then transmitted according to this ordering. However, the sorting of transmission candidates (e.g., packets) according to their finish times and the WFQ finish time calculations are complex and require a large computational overhead, making this scheme costly to implement.